(0) Obligation:

Clauses:

delete(X, tree(X, void, Right), Right).
delete(X, tree(X, Left, void), Left).
delete(X, tree(X, Left, Right), tree(Y, Left, Right1)) :- delmin(Right, Y, Right1).
delete(X, tree(Y, Left, Right), tree(Y, Left1, Right)) :- ','(less(X, Y), delete(X, Left, Left1)).
delete(X, tree(Y, Left, Right), tree(Y, Left, Right1)) :- ','(less(Y, X), delete(X, Right, Right1)).
delmin(tree(Y, void, Right), Y, Right).
delmin(tree(X, Left, X1), Y, tree(X, Left1, X2)) :- delmin(Left, Y, Left1).
less(0, s(X3)).
less(s(X), s(Y)) :- less(X, Y).

Query: delete(g,g,a)

(1) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph DT10.

(2) Obligation:

Triples:

lessF(s(X1)) :- lessF(X1).
pB(X1, X2) :- lessF(X1).
pB(X1, X2) :- ','(lesscF(X1), deleteA(X1, void, X2)).
pC(X1, X2) :- lessF(X1).
pC(X1, X2) :- ','(lesscF(X1), deleteA(s(X1), void, X2)).
delminD(tree(X1, X2, X3), X4, tree(X1, X5, X6)) :- delminD(X2, X4, X5).
pE(X1, X2, X3) :- lessF(X1).
pE(X1, X2, X3) :- ','(lesscF(X1), deleteA(X1, X2, X3)).
lessH(s(X1), s(X2)) :- lessH(X1, X2).
deleteA(X1, tree(X1, void, void), tree(X1, X2, void)) :- pB(X1, X2).
deleteA(X1, tree(X1, void, void), tree(X1, void, X2)) :- pB(X1, X2).
deleteA(s(X1), tree(s(X1), void, void), tree(s(X1), X2, void)) :- pC(X1, X2).
deleteA(X1, tree(X1, void, void), tree(X1, void, X2)) :- pB(X1, X2).
deleteA(s(X1), tree(s(X1), void, void), tree(s(X1), void, X2)) :- pC(X1, X2).
deleteA(X1, tree(X1, void, tree(X2, X3, X4)), tree(X5, void, tree(X2, X6, X7))) :- delminD(X3, X5, X6).
deleteA(X1, tree(X1, void, X2), tree(X1, X3, X2)) :- pB(X1, X3).
deleteA(X1, tree(X1, void, X2), tree(X1, void, X3)) :- pE(X1, X2, X3).
deleteA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) :- lessF(X1).
deleteA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) :- ','(lesscF(X1), deleteA(s(X1), void, X3)).
deleteA(X1, tree(X1, void, X2), tree(X1, void, X3)) :- pE(X1, X2, X3).
deleteA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) :- lessF(X1).
deleteA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) :- ','(lesscF(X1), deleteA(s(X1), X2, X3)).
deleteA(X1, tree(X1, X2, void), tree(X1, X3, void)) :- lessF(X1).
deleteA(X1, tree(X1, X2, void), tree(X1, X3, void)) :- ','(lesscF(X1), deleteA(X1, X2, X3)).
deleteA(X1, tree(X1, X2, void), tree(X1, X2, X3)) :- pB(X1, X3).
deleteA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) :- lessF(X1).
deleteA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) :- ','(lesscF(X1), deleteA(s(X1), X2, X3)).
deleteA(X1, tree(X1, X2, void), tree(X1, X2, X3)) :- pB(X1, X3).
deleteA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) :- lessF(X1).
deleteA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) :- ','(lesscF(X1), deleteA(s(X1), void, X3)).
deleteA(X1, tree(X1, X2, tree(X3, X4, X5)), tree(X6, X2, tree(X3, X7, X8))) :- delminD(X4, X6, X7).
deleteA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) :- lessF(X1).
deleteA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) :- ','(lesscF(X1), deleteA(X1, X2, X4)).
deleteA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) :- lessF(X1).
deleteA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) :- ','(lesscF(X1), deleteA(X1, X3, X4)).
deleteA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- deleteA(0, X2, X4).
deleteA(s(s(s(s(s(s(s(s(X1)))))))), tree(s(s(s(s(s(s(s(s(X2)))))))), X3, X4), tree(s(s(s(s(s(s(s(s(X2)))))))), X5, X4)) :- lessH(X1, X2).
deleteA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- ','(lesscG(X1, X2), deleteA(s(X1), X3, X5)).
deleteA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- lessH(X2, X1).
deleteA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- ','(lesscH(X2, X1), deleteA(X1, X4, X5)).
deleteA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- deleteA(s(X1), X3, X4).
deleteA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- lessH(X2, X1).
deleteA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- ','(lesscH(X2, X1), deleteA(s(X1), X4, X5)).

Clauses:

deletecA(X1, tree(X1, void, X2), X2).
deletecA(X1, tree(X1, void, void), void).
deletecA(X1, tree(X1, void, void), tree(X1, X2, void)) :- qcB(X1, X2).
deletecA(X1, tree(X1, void, void), tree(X1, void, X2)) :- qcB(X1, X2).
deletecA(s(X1), tree(s(X1), void, void), tree(s(X1), X2, void)) :- qcC(X1, X2).
deletecA(X1, tree(X1, void, void), tree(X1, void, X2)) :- qcB(X1, X2).
deletecA(s(X1), tree(s(X1), void, void), tree(s(X1), void, X2)) :- qcC(X1, X2).
deletecA(X1, tree(X1, void, tree(X2, void, X3)), tree(X2, void, X3)).
deletecA(X1, tree(X1, void, tree(X2, X3, X4)), tree(X5, void, tree(X2, X6, X7))) :- delmincD(X3, X5, X6).
deletecA(X1, tree(X1, void, X2), tree(X1, X3, X2)) :- qcB(X1, X3).
deletecA(X1, tree(X1, void, X2), tree(X1, void, X3)) :- qcE(X1, X2, X3).
deletecA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) :- ','(lesscF(X1), deletecA(s(X1), void, X3)).
deletecA(X1, tree(X1, void, X2), tree(X1, void, X3)) :- qcE(X1, X2, X3).
deletecA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) :- ','(lesscF(X1), deletecA(s(X1), X2, X3)).
deletecA(X1, tree(X1, X2, void), X2).
deletecA(X1, tree(X1, X2, void), tree(X1, X3, void)) :- ','(lesscF(X1), deletecA(X1, X2, X3)).
deletecA(X1, tree(X1, X2, void), tree(X1, X2, X3)) :- qcB(X1, X3).
deletecA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) :- ','(lesscF(X1), deletecA(s(X1), X2, X3)).
deletecA(X1, tree(X1, X2, void), tree(X1, X2, X3)) :- qcB(X1, X3).
deletecA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) :- ','(lesscF(X1), deletecA(s(X1), void, X3)).
deletecA(X1, tree(X1, X2, tree(X3, void, X4)), tree(X3, X2, X4)).
deletecA(X1, tree(X1, X2, tree(X3, X4, X5)), tree(X6, X2, tree(X3, X7, X8))) :- delmincD(X4, X6, X7).
deletecA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) :- ','(lesscF(X1), deletecA(X1, X2, X4)).
deletecA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) :- ','(lesscF(X1), deletecA(X1, X3, X4)).
deletecA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) :- deletecA(0, X2, X4).
deletecA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) :- ','(lesscG(X1, X2), deletecA(s(X1), X3, X5)).
deletecA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) :- ','(lesscH(X2, X1), deletecA(X1, X4, X5)).
deletecA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) :- deletecA(s(X1), X3, X4).
deletecA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) :- ','(lesscH(X2, X1), deletecA(s(X1), X4, X5)).
lesscF(s(X1)) :- lesscF(X1).
qcB(X1, X2) :- ','(lesscF(X1), deletecA(X1, void, X2)).
qcC(X1, X2) :- ','(lesscF(X1), deletecA(s(X1), void, X2)).
delmincD(tree(X1, void, X2), X1, X2).
delmincD(tree(X1, X2, X3), X4, tree(X1, X5, X6)) :- delmincD(X2, X4, X5).
qcE(X1, X2, X3) :- ','(lesscF(X1), deletecA(X1, X2, X3)).
lesscH(0, s(X1)).
lesscH(s(X1), s(X2)) :- lesscH(X1, X2).
lesscG(0, s(X1)).
lesscG(s(0), s(s(X1))).
lesscG(s(s(0)), s(s(s(X1)))).
lesscG(s(s(s(0))), s(s(s(s(X1))))).
lesscG(s(s(s(s(0)))), s(s(s(s(s(X1)))))).
lesscG(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))).
lesscG(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))).
lesscG(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) :- lesscH(X1, X2).

Afs:

deleteA(x1, x2, x3)  =  deleteA(x1, x2)

(3) TriplesToPiDPProof (SOUND transformation)

We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:
deleteA_in: (b,b,f)
pB_in: (b,f)
lessF_in: (b)
lesscF_in: (b)
pC_in: (b,f)
delminD_in: (b,f,f)
pE_in: (b,b,f)
lessH_in: (b,b)
lesscG_in: (b,b)
lesscH_in: (b,b)
Transforming TRIPLES into the following Term Rewriting System:
Pi DP problem:
The TRS P consists of the following rules:

DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, X2, void)) → U13_GGA(X1, X2, pB_in_ga(X1, X2))
DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, X2, void)) → PB_IN_GA(X1, X2)
PB_IN_GA(X1, X2) → U2_GA(X1, X2, lessF_in_g(X1))
PB_IN_GA(X1, X2) → LESSF_IN_G(X1)
LESSF_IN_G(s(X1)) → U1_G(X1, lessF_in_g(X1))
LESSF_IN_G(s(X1)) → LESSF_IN_G(X1)
PB_IN_GA(X1, X2) → U3_GA(X1, X2, lesscF_in_g(X1))
U3_GA(X1, X2, lesscF_out_g(X1)) → U4_GA(X1, X2, deleteA_in_gga(X1, void, X2))
U3_GA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, void, X2)
DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, void, X2)) → U14_GGA(X1, X2, pB_in_ga(X1, X2))
DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, void, X2)) → PB_IN_GA(X1, X2)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), X2, void)) → U15_GGA(X1, X2, pC_in_ga(X1, X2))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), X2, void)) → PC_IN_GA(X1, X2)
PC_IN_GA(X1, X2) → U5_GA(X1, X2, lessF_in_g(X1))
PC_IN_GA(X1, X2) → LESSF_IN_G(X1)
PC_IN_GA(X1, X2) → U6_GA(X1, X2, lesscF_in_g(X1))
U6_GA(X1, X2, lesscF_out_g(X1)) → U7_GA(X1, X2, deleteA_in_gga(s(X1), void, X2))
U6_GA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), void, X2)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), void, X2)) → U16_GGA(X1, X2, pC_in_ga(X1, X2))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), void, X2)) → PC_IN_GA(X1, X2)
DELETEA_IN_GGA(X1, tree(X1, void, tree(X2, X3, X4)), tree(X5, void, tree(X2, X6, X7))) → U17_GGA(X1, X2, X3, X4, X5, X6, X7, delminD_in_gaa(X3, X5, X6))
DELETEA_IN_GGA(X1, tree(X1, void, tree(X2, X3, X4)), tree(X5, void, tree(X2, X6, X7))) → DELMIND_IN_GAA(X3, X5, X6)
DELMIND_IN_GAA(tree(X1, X2, X3), X4, tree(X1, X5, X6)) → U8_GAA(X1, X2, X3, X4, X5, X6, delminD_in_gaa(X2, X4, X5))
DELMIND_IN_GAA(tree(X1, X2, X3), X4, tree(X1, X5, X6)) → DELMIND_IN_GAA(X2, X4, X5)
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, X3, X2)) → U18_GGA(X1, X2, X3, pB_in_ga(X1, X3))
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, X3, X2)) → PB_IN_GA(X1, X3)
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, void, X3)) → U19_GGA(X1, X2, X3, pE_in_gga(X1, X2, X3))
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, void, X3)) → PE_IN_GGA(X1, X2, X3)
PE_IN_GGA(X1, X2, X3) → U9_GGA(X1, X2, X3, lessF_in_g(X1))
PE_IN_GGA(X1, X2, X3) → LESSF_IN_G(X1)
PE_IN_GGA(X1, X2, X3) → U10_GGA(X1, X2, X3, lesscF_in_g(X1))
U10_GGA(X1, X2, X3, lesscF_out_g(X1)) → U11_GGA(X1, X2, X3, deleteA_in_gga(X1, X2, X3))
U10_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) → U20_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) → U21_GGA(X1, X2, X3, lesscF_in_g(X1))
U21_GGA(X1, X2, X3, lesscF_out_g(X1)) → U22_GGA(X1, X2, X3, deleteA_in_gga(s(X1), void, X3))
U21_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), void, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → U23_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → U24_GGA(X1, X2, X3, lesscF_in_g(X1))
U24_GGA(X1, X2, X3, lesscF_out_g(X1)) → U25_GGA(X1, X2, X3, deleteA_in_gga(s(X1), X2, X3))
U24_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → U26_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → U27_GGA(X1, X2, X3, lesscF_in_g(X1))
U27_GGA(X1, X2, X3, lesscF_out_g(X1)) → U28_GGA(X1, X2, X3, deleteA_in_gga(X1, X2, X3))
U27_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X2, X3)) → U29_GGA(X1, X2, X3, pB_in_ga(X1, X3))
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X2, X3)) → PB_IN_GA(X1, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → U30_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → U31_GGA(X1, X2, X3, lesscF_in_g(X1))
U31_GGA(X1, X2, X3, lesscF_out_g(X1)) → U32_GGA(X1, X2, X3, deleteA_in_gga(s(X1), X2, X3))
U31_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) → U33_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) → U34_GGA(X1, X2, X3, lesscF_in_g(X1))
U34_GGA(X1, X2, X3, lesscF_out_g(X1)) → U35_GGA(X1, X2, X3, deleteA_in_gga(s(X1), void, X3))
U34_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), void, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, tree(X3, X4, X5)), tree(X6, X2, tree(X3, X7, X8))) → U36_GGA(X1, X2, X3, X4, X5, X6, X7, X8, delminD_in_gaa(X4, X6, X7))
DELETEA_IN_GGA(X1, tree(X1, X2, tree(X3, X4, X5)), tree(X6, X2, tree(X3, X7, X8))) → DELMIND_IN_GAA(X4, X6, X7)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → U37_GGA(X1, X2, X3, X4, lessF_in_g(X1))
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → U38_GGA(X1, X2, X3, X4, lesscF_in_g(X1))
U38_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → U39_GGA(X1, X2, X3, X4, deleteA_in_gga(X1, X2, X4))
U38_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X4)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → U40_GGA(X1, X2, X3, X4, lessF_in_g(X1))
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → U41_GGA(X1, X2, X3, X4, lesscF_in_g(X1))
U41_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → U42_GGA(X1, X2, X3, X4, deleteA_in_gga(X1, X3, X4))
U41_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X3, X4)
DELETEA_IN_GGA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) → U43_GGA(X1, X2, X3, X4, deleteA_in_gga(0, X2, X4))
DELETEA_IN_GGA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) → DELETEA_IN_GGA(0, X2, X4)
DELETEA_IN_GGA(s(s(s(s(s(s(s(s(X1)))))))), tree(s(s(s(s(s(s(s(s(X2)))))))), X3, X4), tree(s(s(s(s(s(s(s(s(X2)))))))), X5, X4)) → U44_GGA(X1, X2, X3, X4, X5, lessH_in_gg(X1, X2))
DELETEA_IN_GGA(s(s(s(s(s(s(s(s(X1)))))))), tree(s(s(s(s(s(s(s(s(X2)))))))), X3, X4), tree(s(s(s(s(s(s(s(s(X2)))))))), X5, X4)) → LESSH_IN_GG(X1, X2)
LESSH_IN_GG(s(X1), s(X2)) → U12_GG(X1, X2, lessH_in_gg(X1, X2))
LESSH_IN_GG(s(X1), s(X2)) → LESSH_IN_GG(X1, X2)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) → U45_GGA(X1, X2, X3, X4, X5, lesscG_in_gg(X1, X2))
U45_GGA(X1, X2, X3, X4, X5, lesscG_out_gg(X1, X2)) → U46_GGA(X1, X2, X3, X4, X5, deleteA_in_gga(s(X1), X3, X5))
U45_GGA(X1, X2, X3, X4, X5, lesscG_out_gg(X1, X2)) → DELETEA_IN_GGA(s(X1), X3, X5)
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → U47_GGA(X1, X2, X3, X4, X5, lessH_in_gg(X2, X1))
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → LESSH_IN_GG(X2, X1)
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → U48_GGA(X1, X2, X3, X4, X5, lesscH_in_gg(X2, X1))
U48_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → U49_GGA(X1, X2, X3, X4, X5, deleteA_in_gga(X1, X4, X5))
U48_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(X1, X4, X5)
DELETEA_IN_GGA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) → U50_GGA(X1, X2, X3, X4, deleteA_in_gga(s(X1), X3, X4))
DELETEA_IN_GGA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) → DELETEA_IN_GGA(s(X1), X3, X4)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → U51_GGA(X1, X2, X3, X4, X5, lessH_in_gg(X2, X1))
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → LESSH_IN_GG(X2, X1)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → U52_GGA(X1, X2, X3, X4, X5, lesscH_in_gg(X2, X1))
U52_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → U53_GGA(X1, X2, X3, X4, X5, deleteA_in_gga(s(X1), X4, X5))
U52_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(s(X1), X4, X5)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

The argument filtering Pi contains the following mapping:
deleteA_in_gga(x1, x2, x3)  =  deleteA_in_gga(x1, x2)
tree(x1, x2, x3)  =  tree(x1, x2, x3)
void  =  void
pB_in_ga(x1, x2)  =  pB_in_ga(x1)
lessF_in_g(x1)  =  lessF_in_g(x1)
s(x1)  =  s(x1)
lesscF_in_g(x1)  =  lesscF_in_g(x1)
U86_g(x1, x2)  =  U86_g(x1, x2)
lesscF_out_g(x1)  =  lesscF_out_g(x1)
pC_in_ga(x1, x2)  =  pC_in_ga(x1)
delminD_in_gaa(x1, x2, x3)  =  delminD_in_gaa(x1)
pE_in_gga(x1, x2, x3)  =  pE_in_gga(x1, x2)
0  =  0
lessH_in_gg(x1, x2)  =  lessH_in_gg(x1, x2)
lesscG_in_gg(x1, x2)  =  lesscG_in_gg(x1, x2)
lesscG_out_gg(x1, x2)  =  lesscG_out_gg(x1, x2)
U95_gg(x1, x2, x3)  =  U95_gg(x1, x2, x3)
lesscH_in_gg(x1, x2)  =  lesscH_in_gg(x1, x2)
lesscH_out_gg(x1, x2)  =  lesscH_out_gg(x1, x2)
U94_gg(x1, x2, x3)  =  U94_gg(x1, x2, x3)
DELETEA_IN_GGA(x1, x2, x3)  =  DELETEA_IN_GGA(x1, x2)
U13_GGA(x1, x2, x3)  =  U13_GGA(x1, x3)
PB_IN_GA(x1, x2)  =  PB_IN_GA(x1)
U2_GA(x1, x2, x3)  =  U2_GA(x1, x3)
LESSF_IN_G(x1)  =  LESSF_IN_G(x1)
U1_G(x1, x2)  =  U1_G(x1, x2)
U3_GA(x1, x2, x3)  =  U3_GA(x1, x3)
U4_GA(x1, x2, x3)  =  U4_GA(x1, x3)
U14_GGA(x1, x2, x3)  =  U14_GGA(x1, x3)
U15_GGA(x1, x2, x3)  =  U15_GGA(x1, x3)
PC_IN_GA(x1, x2)  =  PC_IN_GA(x1)
U5_GA(x1, x2, x3)  =  U5_GA(x1, x3)
U6_GA(x1, x2, x3)  =  U6_GA(x1, x3)
U7_GA(x1, x2, x3)  =  U7_GA(x1, x3)
U16_GGA(x1, x2, x3)  =  U16_GGA(x1, x3)
U17_GGA(x1, x2, x3, x4, x5, x6, x7, x8)  =  U17_GGA(x1, x2, x3, x4, x8)
DELMIND_IN_GAA(x1, x2, x3)  =  DELMIND_IN_GAA(x1)
U8_GAA(x1, x2, x3, x4, x5, x6, x7)  =  U8_GAA(x1, x2, x3, x7)
U18_GGA(x1, x2, x3, x4)  =  U18_GGA(x1, x2, x4)
U19_GGA(x1, x2, x3, x4)  =  U19_GGA(x1, x2, x4)
PE_IN_GGA(x1, x2, x3)  =  PE_IN_GGA(x1, x2)
U9_GGA(x1, x2, x3, x4)  =  U9_GGA(x1, x2, x4)
U10_GGA(x1, x2, x3, x4)  =  U10_GGA(x1, x2, x4)
U11_GGA(x1, x2, x3, x4)  =  U11_GGA(x1, x2, x4)
U20_GGA(x1, x2, x3, x4)  =  U20_GGA(x1, x2, x4)
U21_GGA(x1, x2, x3, x4)  =  U21_GGA(x1, x2, x4)
U22_GGA(x1, x2, x3, x4)  =  U22_GGA(x1, x2, x4)
U23_GGA(x1, x2, x3, x4)  =  U23_GGA(x1, x2, x4)
U24_GGA(x1, x2, x3, x4)  =  U24_GGA(x1, x2, x4)
U25_GGA(x1, x2, x3, x4)  =  U25_GGA(x1, x2, x4)
U26_GGA(x1, x2, x3, x4)  =  U26_GGA(x1, x2, x4)
U27_GGA(x1, x2, x3, x4)  =  U27_GGA(x1, x2, x4)
U28_GGA(x1, x2, x3, x4)  =  U28_GGA(x1, x2, x4)
U29_GGA(x1, x2, x3, x4)  =  U29_GGA(x1, x2, x4)
U30_GGA(x1, x2, x3, x4)  =  U30_GGA(x1, x2, x4)
U31_GGA(x1, x2, x3, x4)  =  U31_GGA(x1, x2, x4)
U32_GGA(x1, x2, x3, x4)  =  U32_GGA(x1, x2, x4)
U33_GGA(x1, x2, x3, x4)  =  U33_GGA(x1, x2, x4)
U34_GGA(x1, x2, x3, x4)  =  U34_GGA(x1, x2, x4)
U35_GGA(x1, x2, x3, x4)  =  U35_GGA(x1, x2, x4)
U36_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U36_GGA(x1, x2, x3, x4, x5, x9)
U37_GGA(x1, x2, x3, x4, x5)  =  U37_GGA(x1, x2, x3, x5)
U38_GGA(x1, x2, x3, x4, x5)  =  U38_GGA(x1, x2, x3, x5)
U39_GGA(x1, x2, x3, x4, x5)  =  U39_GGA(x1, x2, x3, x5)
U40_GGA(x1, x2, x3, x4, x5)  =  U40_GGA(x1, x2, x3, x5)
U41_GGA(x1, x2, x3, x4, x5)  =  U41_GGA(x1, x2, x3, x5)
U42_GGA(x1, x2, x3, x4, x5)  =  U42_GGA(x1, x2, x3, x5)
U43_GGA(x1, x2, x3, x4, x5)  =  U43_GGA(x1, x2, x3, x5)
U44_GGA(x1, x2, x3, x4, x5, x6)  =  U44_GGA(x1, x2, x3, x4, x6)
LESSH_IN_GG(x1, x2)  =  LESSH_IN_GG(x1, x2)
U12_GG(x1, x2, x3)  =  U12_GG(x1, x2, x3)
U45_GGA(x1, x2, x3, x4, x5, x6)  =  U45_GGA(x1, x2, x3, x4, x6)
U46_GGA(x1, x2, x3, x4, x5, x6)  =  U46_GGA(x1, x2, x3, x4, x6)
U47_GGA(x1, x2, x3, x4, x5, x6)  =  U47_GGA(x1, x2, x3, x4, x6)
U48_GGA(x1, x2, x3, x4, x5, x6)  =  U48_GGA(x1, x2, x3, x4, x6)
U49_GGA(x1, x2, x3, x4, x5, x6)  =  U49_GGA(x1, x2, x3, x4, x6)
U50_GGA(x1, x2, x3, x4, x5)  =  U50_GGA(x1, x2, x3, x5)
U51_GGA(x1, x2, x3, x4, x5, x6)  =  U51_GGA(x1, x2, x3, x4, x6)
U52_GGA(x1, x2, x3, x4, x5, x6)  =  U52_GGA(x1, x2, x3, x4, x6)
U53_GGA(x1, x2, x3, x4, x5, x6)  =  U53_GGA(x1, x2, x3, x4, x6)

We have to consider all (P,R,Pi)-chains

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(4) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, X2, void)) → U13_GGA(X1, X2, pB_in_ga(X1, X2))
DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, X2, void)) → PB_IN_GA(X1, X2)
PB_IN_GA(X1, X2) → U2_GA(X1, X2, lessF_in_g(X1))
PB_IN_GA(X1, X2) → LESSF_IN_G(X1)
LESSF_IN_G(s(X1)) → U1_G(X1, lessF_in_g(X1))
LESSF_IN_G(s(X1)) → LESSF_IN_G(X1)
PB_IN_GA(X1, X2) → U3_GA(X1, X2, lesscF_in_g(X1))
U3_GA(X1, X2, lesscF_out_g(X1)) → U4_GA(X1, X2, deleteA_in_gga(X1, void, X2))
U3_GA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, void, X2)
DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, void, X2)) → U14_GGA(X1, X2, pB_in_ga(X1, X2))
DELETEA_IN_GGA(X1, tree(X1, void, void), tree(X1, void, X2)) → PB_IN_GA(X1, X2)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), X2, void)) → U15_GGA(X1, X2, pC_in_ga(X1, X2))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), X2, void)) → PC_IN_GA(X1, X2)
PC_IN_GA(X1, X2) → U5_GA(X1, X2, lessF_in_g(X1))
PC_IN_GA(X1, X2) → LESSF_IN_G(X1)
PC_IN_GA(X1, X2) → U6_GA(X1, X2, lesscF_in_g(X1))
U6_GA(X1, X2, lesscF_out_g(X1)) → U7_GA(X1, X2, deleteA_in_gga(s(X1), void, X2))
U6_GA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), void, X2)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), void, X2)) → U16_GGA(X1, X2, pC_in_ga(X1, X2))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, void), tree(s(X1), void, X2)) → PC_IN_GA(X1, X2)
DELETEA_IN_GGA(X1, tree(X1, void, tree(X2, X3, X4)), tree(X5, void, tree(X2, X6, X7))) → U17_GGA(X1, X2, X3, X4, X5, X6, X7, delminD_in_gaa(X3, X5, X6))
DELETEA_IN_GGA(X1, tree(X1, void, tree(X2, X3, X4)), tree(X5, void, tree(X2, X6, X7))) → DELMIND_IN_GAA(X3, X5, X6)
DELMIND_IN_GAA(tree(X1, X2, X3), X4, tree(X1, X5, X6)) → U8_GAA(X1, X2, X3, X4, X5, X6, delminD_in_gaa(X2, X4, X5))
DELMIND_IN_GAA(tree(X1, X2, X3), X4, tree(X1, X5, X6)) → DELMIND_IN_GAA(X2, X4, X5)
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, X3, X2)) → U18_GGA(X1, X2, X3, pB_in_ga(X1, X3))
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, X3, X2)) → PB_IN_GA(X1, X3)
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, void, X3)) → U19_GGA(X1, X2, X3, pE_in_gga(X1, X2, X3))
DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, void, X3)) → PE_IN_GGA(X1, X2, X3)
PE_IN_GGA(X1, X2, X3) → U9_GGA(X1, X2, X3, lessF_in_g(X1))
PE_IN_GGA(X1, X2, X3) → LESSF_IN_G(X1)
PE_IN_GGA(X1, X2, X3) → U10_GGA(X1, X2, X3, lesscF_in_g(X1))
U10_GGA(X1, X2, X3, lesscF_out_g(X1)) → U11_GGA(X1, X2, X3, deleteA_in_gga(X1, X2, X3))
U10_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) → U20_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), X3, X2)) → U21_GGA(X1, X2, X3, lesscF_in_g(X1))
U21_GGA(X1, X2, X3, lesscF_out_g(X1)) → U22_GGA(X1, X2, X3, deleteA_in_gga(s(X1), void, X3))
U21_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), void, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → U23_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → U24_GGA(X1, X2, X3, lesscF_in_g(X1))
U24_GGA(X1, X2, X3, lesscF_out_g(X1)) → U25_GGA(X1, X2, X3, deleteA_in_gga(s(X1), X2, X3))
U24_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → U26_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → U27_GGA(X1, X2, X3, lesscF_in_g(X1))
U27_GGA(X1, X2, X3, lesscF_out_g(X1)) → U28_GGA(X1, X2, X3, deleteA_in_gga(X1, X2, X3))
U27_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X2, X3)) → U29_GGA(X1, X2, X3, pB_in_ga(X1, X3))
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X2, X3)) → PB_IN_GA(X1, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → U30_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → U31_GGA(X1, X2, X3, lesscF_in_g(X1))
U31_GGA(X1, X2, X3, lesscF_out_g(X1)) → U32_GGA(X1, X2, X3, deleteA_in_gga(s(X1), X2, X3))
U31_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) → U33_GGA(X1, X2, X3, lessF_in_g(X1))
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X2, X3)) → U34_GGA(X1, X2, X3, lesscF_in_g(X1))
U34_GGA(X1, X2, X3, lesscF_out_g(X1)) → U35_GGA(X1, X2, X3, deleteA_in_gga(s(X1), void, X3))
U34_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), void, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, tree(X3, X4, X5)), tree(X6, X2, tree(X3, X7, X8))) → U36_GGA(X1, X2, X3, X4, X5, X6, X7, X8, delminD_in_gaa(X4, X6, X7))
DELETEA_IN_GGA(X1, tree(X1, X2, tree(X3, X4, X5)), tree(X6, X2, tree(X3, X7, X8))) → DELMIND_IN_GAA(X4, X6, X7)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → U37_GGA(X1, X2, X3, X4, lessF_in_g(X1))
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → U38_GGA(X1, X2, X3, X4, lesscF_in_g(X1))
U38_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → U39_GGA(X1, X2, X3, X4, deleteA_in_gga(X1, X2, X4))
U38_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X4)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → U40_GGA(X1, X2, X3, X4, lessF_in_g(X1))
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → LESSF_IN_G(X1)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → U41_GGA(X1, X2, X3, X4, lesscF_in_g(X1))
U41_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → U42_GGA(X1, X2, X3, X4, deleteA_in_gga(X1, X3, X4))
U41_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X3, X4)
DELETEA_IN_GGA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) → U43_GGA(X1, X2, X3, X4, deleteA_in_gga(0, X2, X4))
DELETEA_IN_GGA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) → DELETEA_IN_GGA(0, X2, X4)
DELETEA_IN_GGA(s(s(s(s(s(s(s(s(X1)))))))), tree(s(s(s(s(s(s(s(s(X2)))))))), X3, X4), tree(s(s(s(s(s(s(s(s(X2)))))))), X5, X4)) → U44_GGA(X1, X2, X3, X4, X5, lessH_in_gg(X1, X2))
DELETEA_IN_GGA(s(s(s(s(s(s(s(s(X1)))))))), tree(s(s(s(s(s(s(s(s(X2)))))))), X3, X4), tree(s(s(s(s(s(s(s(s(X2)))))))), X5, X4)) → LESSH_IN_GG(X1, X2)
LESSH_IN_GG(s(X1), s(X2)) → U12_GG(X1, X2, lessH_in_gg(X1, X2))
LESSH_IN_GG(s(X1), s(X2)) → LESSH_IN_GG(X1, X2)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) → U45_GGA(X1, X2, X3, X4, X5, lesscG_in_gg(X1, X2))
U45_GGA(X1, X2, X3, X4, X5, lesscG_out_gg(X1, X2)) → U46_GGA(X1, X2, X3, X4, X5, deleteA_in_gga(s(X1), X3, X5))
U45_GGA(X1, X2, X3, X4, X5, lesscG_out_gg(X1, X2)) → DELETEA_IN_GGA(s(X1), X3, X5)
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → U47_GGA(X1, X2, X3, X4, X5, lessH_in_gg(X2, X1))
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → LESSH_IN_GG(X2, X1)
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → U48_GGA(X1, X2, X3, X4, X5, lesscH_in_gg(X2, X1))
U48_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → U49_GGA(X1, X2, X3, X4, X5, deleteA_in_gga(X1, X4, X5))
U48_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(X1, X4, X5)
DELETEA_IN_GGA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) → U50_GGA(X1, X2, X3, X4, deleteA_in_gga(s(X1), X3, X4))
DELETEA_IN_GGA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) → DELETEA_IN_GGA(s(X1), X3, X4)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → U51_GGA(X1, X2, X3, X4, X5, lessH_in_gg(X2, X1))
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → LESSH_IN_GG(X2, X1)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → U52_GGA(X1, X2, X3, X4, X5, lesscH_in_gg(X2, X1))
U52_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → U53_GGA(X1, X2, X3, X4, X5, deleteA_in_gga(s(X1), X4, X5))
U52_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(s(X1), X4, X5)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

The argument filtering Pi contains the following mapping:
deleteA_in_gga(x1, x2, x3)  =  deleteA_in_gga(x1, x2)
tree(x1, x2, x3)  =  tree(x1, x2, x3)
void  =  void
pB_in_ga(x1, x2)  =  pB_in_ga(x1)
lessF_in_g(x1)  =  lessF_in_g(x1)
s(x1)  =  s(x1)
lesscF_in_g(x1)  =  lesscF_in_g(x1)
U86_g(x1, x2)  =  U86_g(x1, x2)
lesscF_out_g(x1)  =  lesscF_out_g(x1)
pC_in_ga(x1, x2)  =  pC_in_ga(x1)
delminD_in_gaa(x1, x2, x3)  =  delminD_in_gaa(x1)
pE_in_gga(x1, x2, x3)  =  pE_in_gga(x1, x2)
0  =  0
lessH_in_gg(x1, x2)  =  lessH_in_gg(x1, x2)
lesscG_in_gg(x1, x2)  =  lesscG_in_gg(x1, x2)
lesscG_out_gg(x1, x2)  =  lesscG_out_gg(x1, x2)
U95_gg(x1, x2, x3)  =  U95_gg(x1, x2, x3)
lesscH_in_gg(x1, x2)  =  lesscH_in_gg(x1, x2)
lesscH_out_gg(x1, x2)  =  lesscH_out_gg(x1, x2)
U94_gg(x1, x2, x3)  =  U94_gg(x1, x2, x3)
DELETEA_IN_GGA(x1, x2, x3)  =  DELETEA_IN_GGA(x1, x2)
U13_GGA(x1, x2, x3)  =  U13_GGA(x1, x3)
PB_IN_GA(x1, x2)  =  PB_IN_GA(x1)
U2_GA(x1, x2, x3)  =  U2_GA(x1, x3)
LESSF_IN_G(x1)  =  LESSF_IN_G(x1)
U1_G(x1, x2)  =  U1_G(x1, x2)
U3_GA(x1, x2, x3)  =  U3_GA(x1, x3)
U4_GA(x1, x2, x3)  =  U4_GA(x1, x3)
U14_GGA(x1, x2, x3)  =  U14_GGA(x1, x3)
U15_GGA(x1, x2, x3)  =  U15_GGA(x1, x3)
PC_IN_GA(x1, x2)  =  PC_IN_GA(x1)
U5_GA(x1, x2, x3)  =  U5_GA(x1, x3)
U6_GA(x1, x2, x3)  =  U6_GA(x1, x3)
U7_GA(x1, x2, x3)  =  U7_GA(x1, x3)
U16_GGA(x1, x2, x3)  =  U16_GGA(x1, x3)
U17_GGA(x1, x2, x3, x4, x5, x6, x7, x8)  =  U17_GGA(x1, x2, x3, x4, x8)
DELMIND_IN_GAA(x1, x2, x3)  =  DELMIND_IN_GAA(x1)
U8_GAA(x1, x2, x3, x4, x5, x6, x7)  =  U8_GAA(x1, x2, x3, x7)
U18_GGA(x1, x2, x3, x4)  =  U18_GGA(x1, x2, x4)
U19_GGA(x1, x2, x3, x4)  =  U19_GGA(x1, x2, x4)
PE_IN_GGA(x1, x2, x3)  =  PE_IN_GGA(x1, x2)
U9_GGA(x1, x2, x3, x4)  =  U9_GGA(x1, x2, x4)
U10_GGA(x1, x2, x3, x4)  =  U10_GGA(x1, x2, x4)
U11_GGA(x1, x2, x3, x4)  =  U11_GGA(x1, x2, x4)
U20_GGA(x1, x2, x3, x4)  =  U20_GGA(x1, x2, x4)
U21_GGA(x1, x2, x3, x4)  =  U21_GGA(x1, x2, x4)
U22_GGA(x1, x2, x3, x4)  =  U22_GGA(x1, x2, x4)
U23_GGA(x1, x2, x3, x4)  =  U23_GGA(x1, x2, x4)
U24_GGA(x1, x2, x3, x4)  =  U24_GGA(x1, x2, x4)
U25_GGA(x1, x2, x3, x4)  =  U25_GGA(x1, x2, x4)
U26_GGA(x1, x2, x3, x4)  =  U26_GGA(x1, x2, x4)
U27_GGA(x1, x2, x3, x4)  =  U27_GGA(x1, x2, x4)
U28_GGA(x1, x2, x3, x4)  =  U28_GGA(x1, x2, x4)
U29_GGA(x1, x2, x3, x4)  =  U29_GGA(x1, x2, x4)
U30_GGA(x1, x2, x3, x4)  =  U30_GGA(x1, x2, x4)
U31_GGA(x1, x2, x3, x4)  =  U31_GGA(x1, x2, x4)
U32_GGA(x1, x2, x3, x4)  =  U32_GGA(x1, x2, x4)
U33_GGA(x1, x2, x3, x4)  =  U33_GGA(x1, x2, x4)
U34_GGA(x1, x2, x3, x4)  =  U34_GGA(x1, x2, x4)
U35_GGA(x1, x2, x3, x4)  =  U35_GGA(x1, x2, x4)
U36_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U36_GGA(x1, x2, x3, x4, x5, x9)
U37_GGA(x1, x2, x3, x4, x5)  =  U37_GGA(x1, x2, x3, x5)
U38_GGA(x1, x2, x3, x4, x5)  =  U38_GGA(x1, x2, x3, x5)
U39_GGA(x1, x2, x3, x4, x5)  =  U39_GGA(x1, x2, x3, x5)
U40_GGA(x1, x2, x3, x4, x5)  =  U40_GGA(x1, x2, x3, x5)
U41_GGA(x1, x2, x3, x4, x5)  =  U41_GGA(x1, x2, x3, x5)
U42_GGA(x1, x2, x3, x4, x5)  =  U42_GGA(x1, x2, x3, x5)
U43_GGA(x1, x2, x3, x4, x5)  =  U43_GGA(x1, x2, x3, x5)
U44_GGA(x1, x2, x3, x4, x5, x6)  =  U44_GGA(x1, x2, x3, x4, x6)
LESSH_IN_GG(x1, x2)  =  LESSH_IN_GG(x1, x2)
U12_GG(x1, x2, x3)  =  U12_GG(x1, x2, x3)
U45_GGA(x1, x2, x3, x4, x5, x6)  =  U45_GGA(x1, x2, x3, x4, x6)
U46_GGA(x1, x2, x3, x4, x5, x6)  =  U46_GGA(x1, x2, x3, x4, x6)
U47_GGA(x1, x2, x3, x4, x5, x6)  =  U47_GGA(x1, x2, x3, x4, x6)
U48_GGA(x1, x2, x3, x4, x5, x6)  =  U48_GGA(x1, x2, x3, x4, x6)
U49_GGA(x1, x2, x3, x4, x5, x6)  =  U49_GGA(x1, x2, x3, x4, x6)
U50_GGA(x1, x2, x3, x4, x5)  =  U50_GGA(x1, x2, x3, x5)
U51_GGA(x1, x2, x3, x4, x5, x6)  =  U51_GGA(x1, x2, x3, x4, x6)
U52_GGA(x1, x2, x3, x4, x5, x6)  =  U52_GGA(x1, x2, x3, x4, x6)
U53_GGA(x1, x2, x3, x4, x5, x6)  =  U53_GGA(x1, x2, x3, x4, x6)

We have to consider all (P,R,Pi)-chains

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 69 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

LESSH_IN_GG(s(X1), s(X2)) → LESSH_IN_GG(X1, X2)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

Pi is empty.
We have to consider all (P,R,Pi)-chains

(8) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(9) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

LESSH_IN_GG(s(X1), s(X2)) → LESSH_IN_GG(X1, X2)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains

(10) PiDPToQDPProof (EQUIVALENT transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(11) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LESSH_IN_GG(s(X1), s(X2)) → LESSH_IN_GG(X1, X2)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(12) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • LESSH_IN_GG(s(X1), s(X2)) → LESSH_IN_GG(X1, X2)
    The graph contains the following edges 1 > 1, 2 > 2

(13) YES

(14) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

DELMIND_IN_GAA(tree(X1, X2, X3), X4, tree(X1, X5, X6)) → DELMIND_IN_GAA(X2, X4, X5)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

The argument filtering Pi contains the following mapping:
tree(x1, x2, x3)  =  tree(x1, x2, x3)
s(x1)  =  s(x1)
lesscF_in_g(x1)  =  lesscF_in_g(x1)
U86_g(x1, x2)  =  U86_g(x1, x2)
lesscF_out_g(x1)  =  lesscF_out_g(x1)
0  =  0
lesscG_in_gg(x1, x2)  =  lesscG_in_gg(x1, x2)
lesscG_out_gg(x1, x2)  =  lesscG_out_gg(x1, x2)
U95_gg(x1, x2, x3)  =  U95_gg(x1, x2, x3)
lesscH_in_gg(x1, x2)  =  lesscH_in_gg(x1, x2)
lesscH_out_gg(x1, x2)  =  lesscH_out_gg(x1, x2)
U94_gg(x1, x2, x3)  =  U94_gg(x1, x2, x3)
DELMIND_IN_GAA(x1, x2, x3)  =  DELMIND_IN_GAA(x1)

We have to consider all (P,R,Pi)-chains

(15) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(16) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

DELMIND_IN_GAA(tree(X1, X2, X3), X4, tree(X1, X5, X6)) → DELMIND_IN_GAA(X2, X4, X5)

R is empty.
The argument filtering Pi contains the following mapping:
tree(x1, x2, x3)  =  tree(x1, x2, x3)
DELMIND_IN_GAA(x1, x2, x3)  =  DELMIND_IN_GAA(x1)

We have to consider all (P,R,Pi)-chains

(17) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(18) Obligation:

Q DP problem:
The TRS P consists of the following rules:

DELMIND_IN_GAA(tree(X1, X2, X3)) → DELMIND_IN_GAA(X2)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(19) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • DELMIND_IN_GAA(tree(X1, X2, X3)) → DELMIND_IN_GAA(X2)
    The graph contains the following edges 1 > 1

(20) YES

(21) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

LESSF_IN_G(s(X1)) → LESSF_IN_G(X1)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

Pi is empty.
We have to consider all (P,R,Pi)-chains

(22) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(23) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

LESSF_IN_G(s(X1)) → LESSF_IN_G(X1)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains

(24) PiDPToQDPProof (EQUIVALENT transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(25) Obligation:

Q DP problem:
The TRS P consists of the following rules:

LESSF_IN_G(s(X1)) → LESSF_IN_G(X1)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(26) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • LESSF_IN_G(s(X1)) → LESSF_IN_G(X1)
    The graph contains the following edges 1 > 1

(27) YES

(28) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

DELETEA_IN_GGA(X1, tree(X1, void, X2), tree(X1, void, X3)) → PE_IN_GGA(X1, X2, X3)
PE_IN_GGA(X1, X2, X3) → U10_GGA(X1, X2, X3, lesscF_in_g(X1))
U10_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2), tree(s(X1), void, X3)) → U24_GGA(X1, X2, X3, lesscF_in_g(X1))
U24_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, void), tree(X1, X3, void)) → U27_GGA(X1, X2, X3, lesscF_in_g(X1))
U27_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X3)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void), tree(s(X1), X3, void)) → U31_GGA(X1, X2, X3, lesscF_in_g(X1))
U31_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2, X3)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X4, X3)) → U38_GGA(X1, X2, X3, X4, lesscF_in_g(X1))
U38_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2, X4)
DELETEA_IN_GGA(X1, tree(X1, X2, X3), tree(X1, X2, X4)) → U41_GGA(X1, X2, X3, X4, lesscF_in_g(X1))
U41_GGA(X1, X2, X3, X4, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X3, X4)
DELETEA_IN_GGA(0, tree(s(X1), X2, X3), tree(s(X1), X4, X3)) → DELETEA_IN_GGA(0, X2, X4)
DELETEA_IN_GGA(X1, tree(X2, X3, X4), tree(X2, X3, X5)) → U48_GGA(X1, X2, X3, X4, X5, lesscH_in_gg(X2, X1))
U48_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(X1, X4, X5)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X5, X4)) → U45_GGA(X1, X2, X3, X4, X5, lesscG_in_gg(X1, X2))
U45_GGA(X1, X2, X3, X4, X5, lesscG_out_gg(X1, X2)) → DELETEA_IN_GGA(s(X1), X3, X5)
DELETEA_IN_GGA(s(X1), tree(0, X2, X3), tree(0, X2, X4)) → DELETEA_IN_GGA(s(X1), X3, X4)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4), tree(s(X2), X3, X5)) → U52_GGA(X1, X2, X3, X4, X5, lesscH_in_gg(X2, X1))
U52_GGA(X1, X2, X3, X4, X5, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(s(X1), X4, X5)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

The argument filtering Pi contains the following mapping:
tree(x1, x2, x3)  =  tree(x1, x2, x3)
void  =  void
s(x1)  =  s(x1)
lesscF_in_g(x1)  =  lesscF_in_g(x1)
U86_g(x1, x2)  =  U86_g(x1, x2)
lesscF_out_g(x1)  =  lesscF_out_g(x1)
0  =  0
lesscG_in_gg(x1, x2)  =  lesscG_in_gg(x1, x2)
lesscG_out_gg(x1, x2)  =  lesscG_out_gg(x1, x2)
U95_gg(x1, x2, x3)  =  U95_gg(x1, x2, x3)
lesscH_in_gg(x1, x2)  =  lesscH_in_gg(x1, x2)
lesscH_out_gg(x1, x2)  =  lesscH_out_gg(x1, x2)
U94_gg(x1, x2, x3)  =  U94_gg(x1, x2, x3)
DELETEA_IN_GGA(x1, x2, x3)  =  DELETEA_IN_GGA(x1, x2)
PE_IN_GGA(x1, x2, x3)  =  PE_IN_GGA(x1, x2)
U10_GGA(x1, x2, x3, x4)  =  U10_GGA(x1, x2, x4)
U24_GGA(x1, x2, x3, x4)  =  U24_GGA(x1, x2, x4)
U27_GGA(x1, x2, x3, x4)  =  U27_GGA(x1, x2, x4)
U31_GGA(x1, x2, x3, x4)  =  U31_GGA(x1, x2, x4)
U38_GGA(x1, x2, x3, x4, x5)  =  U38_GGA(x1, x2, x3, x5)
U41_GGA(x1, x2, x3, x4, x5)  =  U41_GGA(x1, x2, x3, x5)
U45_GGA(x1, x2, x3, x4, x5, x6)  =  U45_GGA(x1, x2, x3, x4, x6)
U48_GGA(x1, x2, x3, x4, x5, x6)  =  U48_GGA(x1, x2, x3, x4, x6)
U52_GGA(x1, x2, x3, x4, x5, x6)  =  U52_GGA(x1, x2, x3, x4, x6)

We have to consider all (P,R,Pi)-chains

(29) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(30) Obligation:

Q DP problem:
The TRS P consists of the following rules:

DELETEA_IN_GGA(X1, tree(X1, void, X2)) → PE_IN_GGA(X1, X2)
PE_IN_GGA(X1, X2) → U10_GGA(X1, X2, lesscF_in_g(X1))
U10_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2)
DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2)) → U24_GGA(X1, X2, lesscF_in_g(X1))
U24_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2)
DELETEA_IN_GGA(X1, tree(X1, X2, void)) → U27_GGA(X1, X2, lesscF_in_g(X1))
U27_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2)
DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void)) → U31_GGA(X1, X2, lesscF_in_g(X1))
U31_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2)
DELETEA_IN_GGA(X1, tree(X1, X2, X3)) → U38_GGA(X1, X2, X3, lesscF_in_g(X1))
U38_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2)
DELETEA_IN_GGA(X1, tree(X1, X2, X3)) → U41_GGA(X1, X2, X3, lesscF_in_g(X1))
U41_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X3)
DELETEA_IN_GGA(0, tree(s(X1), X2, X3)) → DELETEA_IN_GGA(0, X2)
DELETEA_IN_GGA(X1, tree(X2, X3, X4)) → U48_GGA(X1, X2, X3, X4, lesscH_in_gg(X2, X1))
U48_GGA(X1, X2, X3, X4, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(X1, X4)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4)) → U45_GGA(X1, X2, X3, X4, lesscG_in_gg(X1, X2))
U45_GGA(X1, X2, X3, X4, lesscG_out_gg(X1, X2)) → DELETEA_IN_GGA(s(X1), X3)
DELETEA_IN_GGA(s(X1), tree(0, X2, X3)) → DELETEA_IN_GGA(s(X1), X3)
DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4)) → U52_GGA(X1, X2, X3, X4, lesscH_in_gg(X2, X1))
U52_GGA(X1, X2, X3, X4, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(s(X1), X4)

The TRS R consists of the following rules:

lesscF_in_g(s(X1)) → U86_g(X1, lesscF_in_g(X1))
U86_g(X1, lesscF_out_g(X1)) → lesscF_out_g(s(X1))
lesscG_in_gg(0, s(X1)) → lesscG_out_gg(0, s(X1))
lesscG_in_gg(s(0), s(s(X1))) → lesscG_out_gg(s(0), s(s(X1)))
lesscG_in_gg(s(s(0)), s(s(s(X1)))) → lesscG_out_gg(s(s(0)), s(s(s(X1))))
lesscG_in_gg(s(s(s(0))), s(s(s(s(X1))))) → lesscG_out_gg(s(s(s(0))), s(s(s(s(X1)))))
lesscG_in_gg(s(s(s(s(0)))), s(s(s(s(s(X1)))))) → lesscG_out_gg(s(s(s(s(0)))), s(s(s(s(s(X1))))))
lesscG_in_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1))))))) → lesscG_out_gg(s(s(s(s(s(0))))), s(s(s(s(s(s(X1)))))))
lesscG_in_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1)))))))) → lesscG_out_gg(s(s(s(s(s(s(0)))))), s(s(s(s(s(s(s(X1))))))))
lesscG_in_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2)))))))) → U95_gg(X1, X2, lesscH_in_gg(X1, X2))
lesscH_in_gg(0, s(X1)) → lesscH_out_gg(0, s(X1))
lesscH_in_gg(s(X1), s(X2)) → U94_gg(X1, X2, lesscH_in_gg(X1, X2))
U94_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscH_out_gg(s(X1), s(X2))
U95_gg(X1, X2, lesscH_out_gg(X1, X2)) → lesscG_out_gg(s(s(s(s(s(s(s(X1))))))), s(s(s(s(s(s(s(X2))))))))

The set Q consists of the following terms:

lesscF_in_g(x0)
U86_g(x0, x1)
lesscG_in_gg(x0, x1)
lesscH_in_gg(x0, x1)
U94_gg(x0, x1, x2)
U95_gg(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(31) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • PE_IN_GGA(X1, X2) → U10_GGA(X1, X2, lesscF_in_g(X1))
    The graph contains the following edges 1 >= 1, 2 >= 2

  • U10_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2)
    The graph contains the following edges 1 >= 1, 3 > 1, 2 >= 2

  • DELETEA_IN_GGA(X1, tree(X1, void, X2)) → PE_IN_GGA(X1, X2)
    The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2

  • DELETEA_IN_GGA(s(X1), tree(0, X2, X3)) → DELETEA_IN_GGA(s(X1), X3)
    The graph contains the following edges 1 >= 1, 2 > 2

  • DELETEA_IN_GGA(0, tree(s(X1), X2, X3)) → DELETEA_IN_GGA(0, X2)
    The graph contains the following edges 1 >= 1, 2 > 2

  • U24_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2)
    The graph contains the following edges 2 >= 2

  • DELETEA_IN_GGA(s(X1), tree(s(X1), void, X2)) → U24_GGA(X1, X2, lesscF_in_g(X1))
    The graph contains the following edges 1 > 1, 2 > 1, 2 > 2

  • U27_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2)
    The graph contains the following edges 1 >= 1, 3 > 1, 2 >= 2

  • DELETEA_IN_GGA(X1, tree(X1, X2, void)) → U27_GGA(X1, X2, lesscF_in_g(X1))
    The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2

  • U31_GGA(X1, X2, lesscF_out_g(X1)) → DELETEA_IN_GGA(s(X1), X2)
    The graph contains the following edges 2 >= 2

  • DELETEA_IN_GGA(s(X1), tree(s(X1), X2, void)) → U31_GGA(X1, X2, lesscF_in_g(X1))
    The graph contains the following edges 1 > 1, 2 > 1, 2 > 2

  • U38_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X2)
    The graph contains the following edges 1 >= 1, 4 > 1, 2 >= 2

  • DELETEA_IN_GGA(X1, tree(X1, X2, X3)) → U38_GGA(X1, X2, X3, lesscF_in_g(X1))
    The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2, 2 > 3

  • U41_GGA(X1, X2, X3, lesscF_out_g(X1)) → DELETEA_IN_GGA(X1, X3)
    The graph contains the following edges 1 >= 1, 4 > 1, 3 >= 2

  • DELETEA_IN_GGA(X1, tree(X1, X2, X3)) → U41_GGA(X1, X2, X3, lesscF_in_g(X1))
    The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2, 2 > 3

  • U48_GGA(X1, X2, X3, X4, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(X1, X4)
    The graph contains the following edges 1 >= 1, 5 > 1, 4 >= 2

  • DELETEA_IN_GGA(X1, tree(X2, X3, X4)) → U48_GGA(X1, X2, X3, X4, lesscH_in_gg(X2, X1))
    The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3, 2 > 4

  • U45_GGA(X1, X2, X3, X4, lesscG_out_gg(X1, X2)) → DELETEA_IN_GGA(s(X1), X3)
    The graph contains the following edges 3 >= 2

  • U52_GGA(X1, X2, X3, X4, lesscH_out_gg(X2, X1)) → DELETEA_IN_GGA(s(X1), X4)
    The graph contains the following edges 4 >= 2

  • DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4)) → U45_GGA(X1, X2, X3, X4, lesscG_in_gg(X1, X2))
    The graph contains the following edges 1 > 1, 2 > 2, 2 > 3, 2 > 4

  • DELETEA_IN_GGA(s(X1), tree(s(X2), X3, X4)) → U52_GGA(X1, X2, X3, X4, lesscH_in_gg(X2, X1))
    The graph contains the following edges 1 > 1, 2 > 2, 2 > 3, 2 > 4

(32) YES